// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-23 16:38
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.TREE;

import org.junit.jupiter.api.Test;

import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class FindKthNumber {
    public int findKthNumber(int n, int k) {
        int ans = 1;
        while (k > 1) {
            int cnt = getCnt(ans, n);
            if (cnt < k) {
                k -= cnt;
                ans++;
            } else {
                k--;
                ans *= 10;
            }
        }
        return ans;
    }

    int getCnt(int x, int limit) {
        String a = String.valueOf(x), b = String.valueOf(limit);
        int n = a.length(), m = b.length(), k = m - n;
        int ans = 0, u = Integer.parseInt(b.substring(0, n));
        for (int i = 0; i < k; i++) {
            ans += Math.pow(10, i);
        }
        if (u > x) {
            /*-----以当前数字开始的数字都存在即x***都存在-----*/
            ans += Math.pow(10, k);
        } else if (u == x) {
            /*-----前缀数字相同，可能出现k == 0的情况-----*/
            ans += limit - x * Math.pow(10, k) + 1;
        }
        return ans;
    }

    @Test
    public void shout() {
        int n = 4289384, k = 1922239;
        System.out.println(findKthNumber(n, k));
    }
}
